package history

func getSqrt(n int) int {
	var right = n
	var left = 0
	for left <= right {
		var mid = left + (right-left)/2
		var sqre = mid * mid
		if sqre == n {
			return mid
		} else if sqre > n {
			if (mid-1)*(mid-1) < n {
				return mid - 1
			}
			right = mid - 1
		} else {
			if (mid+1)*(mid+1) > n {
				return mid
			}
			left = mid + 1
		}
	}
	return -1
}
